package num05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leecode438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> integers = new ArrayList<>();
        int slong = s.length();
         int plong = p.length();

        if (slong < plong){
            return new ArrayList<Integer>();
        }
        int[] snums = new int[26];
        int[] pnums = new int[26];
        //初始化滑动窗口并且判断是否是异位词
        for (int i = 0; i <p.length() ; i++) {
            //初始化滑动窗口哦数组，并计算字母出现的频率
            snums[s.charAt(i) - 'a']++;
            //初始化p字符串数组并记录字母出现的频率
            pnums[p.charAt(i) -'a']++;
        }
        //如果初始即是异位词的话，将对应的开始索引放入集合
        if (Arrays.equals(snums,pnums)){
            integers.add(0);
        }
        for (int i = 0; i < slong-plong; i++) {
            //将原先初始化的数组的起始元素减去（滑动窗口左边减一位）
            snums[s.charAt(i)-'a']--;
            //新加入元素（滑动窗口右边加一位）
            snums[s.charAt(i+plong)-'a']++;
            //如果连个数组相等则位异位词
            if (Arrays.equals(snums,pnums)){
                integers.add(i+1);
            }
        }



      return integers;
    }

    public static void main(String[] args) {
        Leecode438 leecode438 = new Leecode438();
        List<Integer> anagrams = leecode438.findAnagrams("cbaebabacd", "abc");
        System.out.println(anagrams);

    }
}
